#pragma warning(disable:4996)
#pragma warning(disable:4146)
#include <gmp.h>
#include <stdio.h>
//#pragma comment(lib, "libgmp-6.1.1.lib")
//using namespace std;
//#define DEBUG 1

void expmod(mpz_t e, mpz_t m, mpz_t p, mpz_t q)
{
    //int result=1;
    mpz_t result, n, etemp;
    //n=p*q;
    mpz_init(n);
    mpz_mul(n, p, q);
    mpz_init(etemp);
    mpz_init_set_ui(result,1);
    while(mpz_cmp_ui(e, 0) != 0)
    {
        //if((e%0x2)==1)
        mpz_mod_ui(etemp, e, 2);
        if (mpz_cmp_ui(etemp, 1) == 0)
        {
            mpz_mul(result, result, m);
            mpz_mod(result, result, n);
            //result = (result * m)mod pq;
        }
        mpz_mul(m,m, m);
        mpz_mod(m,m, n);
        //m = (m^2)mod pq;
        //e = e >> 1;
        mpz_div_ui(e, e, 2);
    }
    gmp_printf("%Zd\n", result);
}

int main()
{
    int n;
    //freopen("2.in", "r", stdin);
    mpz_t e, m, p, q;
    mpz_init(e);
    mpz_init(m);
    mpz_init(p);
    mpz_init(q);
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        gmp_scanf("%Zd%Zd%Zd%Zd", e, m, p, q);
        expmod(e, m, p, q);
    }
    return 0;
}